import UIKit

func bubbleSort(_ array: inout [Int]) {
  var n = array.count
  for i in 0 ..< n { // 外循环 : 一趟归位一个最大值,需要n - 1 趟可以排序完成
    // 添加一个交换变量 检查数组是否本来就已经排序好的: 如果swapped==true,说明发生交换否则,说明本身就是排序好了的数组,不用进行后续多趟排序
    var swapped = false

    for j in 0 ..< n - 1 - i { // 内循环
      if array[j] > array[j + 1] {
        array.swapAt(j, j + 1)
        swapped = true
      }
    }
    if !swapped { // 如果未发生交换,数组已有序,提前结束
      break
    }
  }
}

// 内循环
// 不优化是:for i in 0..< count - 1
// 优化是:for i in 0 ..< count - 1 - i:
// 假设某一趟比较相邻两个数时,最多(i==0趟时,)能比较n-1次.防止数组越界 0..<n-1,j是比较次序号
// 这是优化后的:外层循环第i次,就归位了i个数字.这i个数字不用再排序了.只需要count-1-i次比较即可
// 示例
// 第一趟(i=0): 7个数,两两比较总计6次,得到最大数90
// 第二趟(i=1): 6个数,两两比较总计5次,7-1-i次
// 第i趟(i=1): 6个数,两两比较总计n-1-i次

var numbers = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(&numbers)
print(numbers) // 输出: [11, 12, 22, 25, 34, 64, 90]

// 0..<0 合法

//////////冒泡排序的原理:使用两个函数实现(没优化)
var nums = [3, 2, 4, 1, 6, 9]
// 一趟冒泡
func bubbleOnce(_ arr: inout [Int]) {
  let count = arr.count
  for i in 0 ..< count - 1 {
    if arr[i] > arr[i + 1] {
      arr.swapAt(i, i + 1)
    }
  }
}

// 冒泡n-1趟
func bubbleN(_ arr: inout [Int]) {
  let count = arr.count
  for j in 0 ..< count - 1 {
    bubbleOnce(&arr)
  }
}

bubbleN(&nums)
print(nums)


//测试
func mBubble(_ arr: inout [Int]) {
  let n = arr.count
  for i in 0 ..< n - 1 {
    var swapped = false
    for j in 0 ..< n - 1 - i {
      if arr[j] > arr[j + 1] {
        arr.swapAt(j, j + 1)
        swapped = true
      }
    }
    if swapped == false {
      break
    }
  }
}

//var aint = [50,241,1,2,3,4,5]
var aint = [1, 2, 3, 5, 4]
mBubble(&aint)
print(aint)
